package com.leetcode.algorithm.y21.m06;

/**
 * leetcode-cn.com 
 * (done)392. 判断子序列
 * (done)1025. 除数博弈
 * (done)1137. 第 N 个泰波那契数
 * (done)1646. 获取生成数组中的最大值
 * (TODO)33. 搜索旋转排序数组
 * 
 * @author jie.deng
 * @date 2021/06/26
 */
public class MySolution0626 {
	
	/**
	 * 392. 判断子序列
	 * 
   * 给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
   * 
   * 字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。
   * 
   * 进阶：
   * 
   * 如果有大量输入的 S，称作 S1, S2, ... , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？
   * 
   * 致谢：
   * 
   * 特别感谢 @pbrother 添加此问题并且创建所有测试用例。
   * 
   *  
   * 
   * 示例 1：
   * 
   * 输入：s = "abc", t = "ahbgdc"
   * 输出：true
   * 示例 2：
   * 
   * 输入：s = "axc", t = "ahbgdc"
   * 输出：false
   *  
   * 
   * 提示：
   * 
   * 0 <= s.length <= 100
   * 0 <= t.length <= 10^4
   * 两个字符串都只由小写字符组成。
   * 
   * 来源：力扣（LeetCode）
   * 链接：https://leetcode-cn.com/problems/is-subsequence
   * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
	 * 
	 * @param s
	 * @param t
	 * @return
	 */
	public boolean isSubsequence(String s, String t) {
		int si = 0;
		int ti = 0;
		for (; si < s.length(); si++) {
			char ch = s.charAt(si);
			boolean match = false;
			for (; ti < t.length(); ti++) {
				if (ch == t.charAt(ti)) {
					match = true;
					ti++;
					break;
				}
			}
			if (!match) {
				break;
			}
		}
		return si == s.length();
	}
    
    /**
     * 1025. 除数博弈
     * 
     * 爱丽丝和鲍勃一起玩游戏，他们轮流行动。爱丽丝先手开局。
     * 
     * 最初，黑板上有一个数字 N 。在每个玩家的回合，玩家需要执行以下操作：
     * 
     * 选出任一 x，满足 0 < x < N 且 N % x == 0 。
     * 用 N - x 替换黑板上的数字 N 。
     * 如果玩家无法执行这些操作，就会输掉游戏。
     * 
     * 只有在爱丽丝在游戏中取得胜利时才返回 True，否则返回 False。假设两个玩家都以最佳状态参与游戏。
     * 
     *  
     * 
     * 示例 1：
     * 
     * 输入：2
     * 输出：true
     * 解释：爱丽丝选择 1，鲍勃无法进行操作。
     * 示例 2：
     * 
     * 输入：3
     * 输出：false
     * 解释：爱丽丝选择 1，鲍勃也选择 1，然后爱丽丝无法进行操作。
     *  
     * 
     * 提示：
     * 
     * 1 <= N <= 1000
     * 
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/divisor-game
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     * 
     * @param n
     * @return
     */
    public boolean divisorGame(int n) {
    	return n % 2 == 0;
    }
  
    
    /**
     * 
     * 1137. 第 N 个泰波那契数
     * 
     * 泰波那契序列 Tn 定义如下： 
     * 
     * T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2
     * 
     * 给你整数 n，请返回第 n 个泰波那契数 Tn 的值。
     * 
     *  
     * 
     * 示例 1：
     * 
     * 输入：n = 4
     * 输出：4
     * 解释：
     * T_3 = 0 + 1 + 1 = 2
     * T_4 = 1 + 1 + 2 = 4
     * 示例 2：
     * 
     * 输入：n = 25
     * 输出：1389537
     *  
     * 
     * 提示：
     * 
     * 0 <= n <= 37
     * 答案保证是一个 32 位整数，即 answer <= 2^31 - 1。
     * 
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/n-th-tribonacci-number
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     * 
     * @param n
     * @return
     */
    public int tribonacci(int n) {
    	if (n == 0) {
    		return 0;
    	}
    	if (n == 1 || n == 2) {
    		return 1;
    	}
    	int[] dp = new int[3];
    	dp[0]=0;
    	dp[1]=1;
    	dp[2]=1;
    	for (int i=3;i<=n;i++) {
			dp[i%3] = dp[0]+dp[1]+dp[2];
		}
    	return dp[n%3];
    }
	public int tribonacci01(int n) {
		if (n == 0) {
			return 0;
		}
		if (n == 1 || n == 2) {
			return 1;
		}
		int[] arr = new int[n + 1];
		int i = 0;
		arr[i++] = 0;
		arr[i++] = 1;
		arr[i++] = 1;
		for (; i < arr.length; i++) {
			arr[i] = arr[i - 1] + arr[i - 2] + arr[i - 3];
		}
		return arr[n];
	}
    
    
    /**
     * 1646. 获取生成数组中的最大值
     * 
     * 给你一个整数 n 。按下述规则生成一个长度为 n + 1 的数组 nums ：
     * 
     * nums[0] = 0
     * nums[1] = 1
     * 当 2 <= 2 * i <= n 时，nums[2 * i] = nums[i]
     * 当 2 <= 2 * i + 1 <= n 时，nums[2 * i + 1] = nums[i] + nums[i + 1]
     * 返回生成数组 nums 中的 最大 值。
     * 
     *  
     * 
     * 示例 1：
     * 
     * 输入：n = 7
     * 输出：3
     * 解释：根据规则：
     *   nums[0] = 0
     *   nums[1] = 1
     *   nums[(1 * 2) = 2] = nums[1] = 1
     *   nums[(1 * 2) + 1 = 3] = nums[1] + nums[2] = 1 + 1 = 2
     *   nums[(2 * 2) = 4] = nums[2] = 1
     *   nums[(2 * 2) + 1 = 5] = nums[2] + nums[3] = 1 + 2 = 3
     *   nums[(3 * 2) = 6] = nums[3] = 2
     *   nums[(3 * 2) + 1 = 7] = nums[3] + nums[4] = 2 + 1 = 3
     * 因此，nums = [0,1,1,2,1,3,2,3]，最大值 3
     * 示例 2：
     * 
     * 输入：n = 2
     * 输出：1
     * 解释：根据规则，nums[0]、nums[1] 和 nums[2] 之中的最大值是 1
     * 示例 3：
     * 
     * 输入：n = 3
     * 输出：2
     * 解释：根据规则，nums[0]、nums[1]、nums[2] 和 nums[3] 之中的最大值是 2
     *  
     * 
     * 提示：
     * 
     * 0 <= n <= 100
     * 
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/get-maximum-in-generated-array
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 
     * 
     * @param n
     * @return
     */
    public int getMaximumGenerated(int n) {
		if (n == 0) {
			return 0;
		}
		if (n == 1) {
			return 1;
		}
		int[] arr = new int[n + 1];
		arr[0]=0;
		arr[1]=1;
		int max = 1;
		for (int i = 1; i*2+1 <= n; i++) {
			int i2 = 2*i;
			arr[i2] = arr[i];
			arr[i2+1] = arr[i]+arr[i+1];
			if (arr[i2+1] > max) {
				max = arr[i2+1];
			}
		}
    	
		return max;
    }
    
    
    /**
     * 33. 搜索旋转排序数组
     * 
     * 整数数组 nums 按升序排列，数组中的值 互不相同 。
     * 
     * 在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
     * 
     * 给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。
     * 
     *  
     * 
     * 示例 1：
     * 
     * 输入：nums = [4,5,6,7,0,1,2], target = 0
     * 输出：4
     * 示例 2：
     * 
     * 输入：nums = [4,5,6,7,0,1,2], target = 3
     * 输出：-1
     * 示例 3：
     * 
     * 输入：nums = [1], target = 0
     * 输出：-1
     *  
     * 
     * 提示：
     * 
     * 1 <= nums.length <= 5000
     * -10^4 <= nums[i] <= 10^4
     * nums 中的每个值都 独一无二
     * 题目数据保证 nums 在预先未知的某个下标上进行了旋转
     * -10^4 <= target <= 10^4
     *  
     * 
     * 进阶：你可以设计一个时间复杂度为 O(log n) 的解决方案吗？
     * 
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/search-in-rotated-sorted-array
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     * 
     * @param nums
     * @param target
     * @return
     */
    public int search(int[] nums, int target) {
		return target;
    }
    
}
